package demo.practice.leetcode;

import java.util.Stack;

public class P137 {

    //https://leetcode-cn.com/problems/binary-search-tree-iterator/
    public static void main(String[] args) {
        //      3
        //    1  4
        //     2
        TreeNode r = new TreeNode(3);
        r.left = new TreeNode(1);
        r.right = new TreeNode(4);
        r.left.right = new TreeNode(2);

        P137 p137 = new P137(r);
//        int next = p137.next();
        System.out.println(p137.next());
        System.out.println(p137.next());
        System.out.println(p137.next());
        System.out.println(p137.next());


    }

    TreeNode root;
    Stack<TreeNode> nodes = new Stack<>();


    public P137(TreeNode root) {
        this.root = root;
        foreach(root);
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        return nodes.pop().val;
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return nodes.size() == 0;
    }


    private void foreach(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.right != null) {
            foreach(root.right);
        }


        nodes.push(root);

        if (root.left != null) {
            foreach(root.left);
        }
    }

}
